package com.company.test24;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created by Administrator on 2016.10.20.
 */
public class Test2412 {
    public static void cardinalSort(int[] list){

        int baseNumber=1;
        while (true){
            int[][] bucket=new int[10][list.length];

            int[] sign=new int[10];

            for(int i=0;i<list.length;i++){
                int current=list[i]/baseNumber%10;
                bucket[current][sign[current]++]=list[i];
            }

            int k=0;
            for(int i=0;i<bucket.length;i++){
                for(int j=0;j<sign[i];j++){
                    list[k++]=bucket[i][j];
                }
            }

            if(sign[0]==list.length){
                break;
            }

            baseNumber=baseNumber*10;
        }
    }
}